package com.zwy.leetcode;

import java.util.*;

public class Day08Test {
    /**
     * 18. 四数之和
     * @param nums
     * @param target
     * @return
     */
    List<List<Integer>> res=new LinkedList<List<Integer>>();
    int count=0;
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if(nums.length<4)return res;
        Arrays.sort(nums);
        LinkedList list=new LinkedList<Integer>();
        backTrack(nums,list,0,target);

        Set<List<Integer>>set=new HashSet<List<Integer>>(res);
        res.clear();
        res.addAll(set);
        return  res;
    }
    public void backTrack(int []nums,LinkedList<Integer>list,int start,int target){
        if(list.size()==4){
            if(count==target)
                res.add(new LinkedList<>(list));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if(nums.length - i  < 4 - list.size())return;
            if(start != i && nums[i - 1] == nums[i])continue;
            if(i < nums.length - 1 && count + nums[i] + (3 - list.size()) * nums[i + 1] > target)return;
            if(i < nums.length - 1 && count + nums[i] + (3 - list.size()) * nums[nums.length - 1] < target)continue;
            count += nums[i];
            list.add(nums[i]);
            backTrack(nums,list,i+1,target);
            list.removeLast();
            count-=nums[i];
        }
    }


    /**
     * 15. 三数之和
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
       int left=0;
       int right=0;
        for (int i = 0; i < nums.length; i++) {

        }
           return null;
        }

    public static void main(String[] args) {
        int []arr={-5,5,4,-3,0,0,4,-2};
        int target=4;
        Day08Test test=new Day08Test();
        List<List<Integer>> lists = test.fourSum(arr, target);
        System.out.println(lists);
    }
}
